package leetcode.editor.cn.dsa15_stackAndGA;
// 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。
// 需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

import java.util.Stack;

public class RemoveDuplicateLetters316_3 {
    public static void main(String[] args) {
        Solution solution = new RemoveDuplicateLetters316_3().new Solution();
        System.out.println(solution.removeDuplicateLetters("bcabc")); //abc
        System.out.println(solution.removeDuplicateLetters("cbacdcbc")); //acdb
        System.out.println(solution.removeDuplicateLetters("dcbadd")); //cbad
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 栈 + 贪心算法
         * 使用数组模拟栈
         */
        public String removeDuplicateLetters(String s) {
            // 使用字符数组来模拟栈， top记录栈顶元素的下标（top=-1时栈为空）
            char[] stack = new char[26];
            int top = -1;
            // 记录当前栈中已经存在的字符，方便对重复元素的判断
            boolean[] seen = new boolean[26];
            // 记录字符串中出现过的字符在字符串最后一次出现的位置
            int[] lastOccurrence = new int[26];
            char[] cs = s.toCharArray();
            int len = cs.length;
            for (int i = 0; i < len; i++) {
                lastOccurrence[cs[i] - 'a'] = i;
            }
            // 从左到右扫描字符串
            for (int i = 0; i < len; i++) {
                char c = cs[i];
                if (!seen[c-'a']) { // 若当前字符已经在栈中，无需处理
                    // 如果栈中有元素，且栈顶元素比当前字符大，并且栈顶字符在后续字符串还会出现：
                    // 那么我们可以用当前字符替换栈顶字符得到一个字典序更小的字符串（此处将一直与栈顶
                    // 元素相比，直到栈为空或栈顶字符比当前字符小，或栈顶字符在当前位置之后不会再出现）
                    while (top != -1 && c < stack[top]
                            && lastOccurrence[stack[top] - 'a'] > i) {
                        seen[stack[top--]-'a'] = false;
                    }
                    // 其他情况都需入栈
                    stack[++top] = c;
                    seen[c-'a'] = true;
                }
            }
            // 将栈中的字母连接起来
            StringBuilder result = new StringBuilder();
            for(int i = 0; i <= top; i++) {
                result.append(stack[i]);
            }
            return result.toString();
            // return new String(stack, 0, top + 1);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}